//搜索旋转数组。给定一个排序后的数组，包含n个整数，但这个数组已被旋转过很多次了，次数不详。请编写代码找出数组中的某个元素，假设数组元素原先是按升序排列的。若
//有多个相同元素，返回索引值最小的一个。 
//
// 示例 1： 
//
// 
// 输入：arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5
// 输出：8（元素5在该数组中的索引）
// 
//
// 示例 2： 
//
// 
// 输入：arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 11
// 输出：-1 （没有找到）
// 
//
// 提示: 
//
// 
// arr 长度范围在[1, 1000000]之间 
// 
//
// Related Topics 数组 二分查找 👍 140 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2025-09-01 22:50:00
 * @description 面试题 10.03.搜索旋转数组
 */
public class SearchRotateArrayLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 SearchRotateArrayLcci fun=new SearchRotateArrayLcci();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 // 也可以用二分，如果有多个一样的，需要返回索引最小的
	//相关题目 189 153 154 33 81 10.03
    public int search(int[] nums, int target) {
		int l=0,r=nums.length-1;
		while (l<=r){
			// 如果有符合的，直接返回，因为找最小的
			if(nums[l]==target) return l;
			int m=(l+r)/2;
			//如果中间值符合，继续往左找
			if(nums[m]==target){
				r=m;
				//左边有序
			}else if(nums[0]<nums[m]){
				if(nums[0]<=target&&target<nums[m]){
					r=m-1;
				}else {
					l=m+1;
				}
				//右边有序
			}else if(nums[0]>nums[m]){
				if(nums[m]<target&&target<=nums[nums.length-1]){
					l=m+1;
				}else {
					r=m-1;
				}
				//中间和左边数字相等，但是不等于target,左移左边界
			}else {
				l+=1;
			}
		}
		return -1;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
